#include<cstdio>
#include<cstring>
typedef unsigned char uint8_t;
typedef unsigned uint32_t;
typedef unsigned long long uint64_t;
template <typename num> inline num rol(num n, int b) {
  return (n<<b)|(n>>((sizeof(n)*8) - b));
}
template <typename num> inline num gcd(num a, num b) {
  if (a * b == 0) return 1;
  while((a%=b)&&(b%=a));
  return a+b;
}
void sha1(uint8_t buf[], uint64_t len) {
  uint64_t pad = len * 8;
  buf[len++] = 0x80;
  int i, j, n = (64 - (len + 8)%64)%64;
  while (n--) buf[len++] = 0;
  for (i = 0;i < 8;i++)
    buf[len+7-i] = pad>>(i*8);
  len += 8;
  uint32_t h[] = {0x67452301u, 0xEFCDAB89u,
    0x98BADCFEu, 0x10325476u, 0xC3D2E1F0u};
  for (i = 0;i < len;i += 64) {
    uint32_t f, k, w[80];
    for (j = 0;j < 16;++j) {
      k = buf[i+j*4];
      buf[i+j*4] = buf[i+j*4+3];
      buf[i+j*4+3] = k;
      k = buf[i+j*4+1];
      buf[i+j*4+1] = buf[i+j*4+2];
      buf[i+j*4+2] = k;
    }
    memcpy(w, buf + i, 64);    
    for (j = 16;j < 80;++j)
      w[j] = rol(w[j-3]^w[j-8]^w[j-14]^w[j-16], 1);
    uint32_t g[5];
    uint32_t &a = g[0], &b = g[1], &c = g[2], &d = g[3], &e = g[4];
    memcpy(g, h, sizeof(h));
    for (j = 0;j < 80;++j) {
      if (j < 20)
        k = 0x5A827999u, f = (b&c)|(d&~b);
      else if (j < 40)
        k = 0x6ED9EBA1u, f = b^c^d;
      else if (j < 60)
        k = 0x8F1BBCDCu, f = (b&c)|(b&d)|(c&d);
      else
        k = 0xCA62C1D6u, f = b^c^d;
      f = rol(a, 5) + f + e + k + w[j];
      for (k = 4;k > 0;--k)
        g[k] = g[k-1];
      a = f;
      c = rol(c, 30);
    }
    for (j = 0;j < 5;++j)
      h[j] += g[j];
  }
  memcpy(buf, h, sizeof(h));
  for (uint32_t j = 0;j < 20;++j) {
    uint32_t k = buf[j*4];
    buf[j*4] = buf[j*4+3];
    buf[j*4+3] = k;
    k = buf[j*4+1];
    buf[j*4+1] = buf[j*4+2];
    buf[j*4+2] = k;
  }  
}
const uint8_t t0[] ={
	0x3A,0x3F,0x3E,0x72,0xBD,0xA2,0xD6,0xB4,0x63,0xC0,0x6E,0x62,0x59,0x1E,0xE2,0x71,
	0xB5,0x0D,0xE8,0x0C,0x25,0x38,0xCE,0x23,0x7C,0xB7,0xAD,0x16,0xDF,0x47,0x3D,0xB3,
	0x7E,0x8C,0xAA,0x61,0x31,0x66,0xBE,0x4F,0x97,0x14,0x54,0xF0,0x70,0xEB,0x30,0xC4,
	0x27,0x4E,0xFA,0x1A,0x2B,0x11,0xF4,0x45,0x8E,0x5D,0x73,0xED,0x22,0x2E,0x7D,0xA4,
	0x28,0xDA,0x2F,0xC5,0x92,0x09,0x05,0x13,0x9D,0x32,0x51,0x4A,0xC8,0xBA,0x96,0xA7,
	0x6A,0x50,0xF3,0xBC,0x93,0xBF,0xB0,0xD2,0xD5,0x82,0x19,0x98,0x35,0xCF,0x6B,0xB6,
	0x83,0x56,0x15,0xF2,0x9A,0x9C,0xCA,0x74,0x34,0x58,0x8D,0xA6,0x03,0xFF,0x46,0x7B,
	0xD0,0x7A,0x33,0x76,0xDD,0xAC,0xCB,0x24,0x7F,0xB1,0x85,0x60,0xC3,0x26,0x8A,0x1D,
	0x1C,0x8F,0x2A,0xEF,0x06,0xDE,0x67,0x5E,0xE7,0xAE,0xD9,0xCC,0x07,0x6C,0xF8,0x0A,
	0xD3,0x40,0x36,0x1F,0x2D,0x95,0x43,0xDB,0x01,0x89,0x4B,0xF7,0xB9,0x39,0xC2,0x52,
	0x53,0xFD,0x65,0xF5,0x68,0xC1,0xC7,0x9F,0x4D,0xEA,0xAF,0x6D,0x10,0x44,0x87,0xD8,
	0xEE,0x1B,0xFE,0x3C,0xDC,0x84,0x69,0x48,0x6F,0xD1,0x57,0x55,0xD4,0xA5,0x49,0x5B,
	0xE5,0x0B,0x94,0xC9,0x5F,0xE1,0x17,0x81,0xBB,0xEC,0xD7,0xC6,0x02,0x4C,0x42,0x75,
	0xA3,0x99,0xE4,0xA1,0x9B,0x5A,0xF1,0x29,0xA0,0x64,0x9E,0x18,0x41,0x80,0x2C,0x79,
	0x20,0x8B,0xAB,0x90,0x08,0xB8,0xA9,0x77,0x12,0xF9,0x0E,0x88,0xE9,0x04,0xFB,0x86,
	0x0F,0xE0,0xA8,0x5C,0xE6,0x21,0xCD,0x3B,0x00,0x78,0xFC,0xF6,0xE3,0x37,0xB2,0x91  
  },t1[] ={
	0xF3,0xE4,0x1B,0x38,0xE5,0x6F,0xE8,0x9D,0x3E,0x55,0xBA,0xC7,0xAC,0xEA,0x66,0xA2,
	0xB9,0x7A,0x34,0x43,0x02,0x4E,0xFE,0x36,0x41,0x57,0x1A,0xB1,0x31,0x87,0x04,0x52,
	0x21,0x22,0xE1,0x13,0x7F,0x03,0x3A,0x90,0xF7,0x69,0x78,0x12,0x83,0x0B,0x9A,0x97,
	0x4D,0xB7,0x8C,0xBF,0x2D,0x94,0xD1,0x93,0x2F,0x42,0x23,0xA4,0xE0,0x92,0xDC,0x68,
	0xD3,0xDD,0xAF,0x91,0x9F,0xED,0x3D,0x8F,0xA1,0x51,0xD9,0xE9,0x70,0x28,0xEF,0xB3,
	0x49,0xA5,0x0D,0xC5,0xD0,0x60,0xB4,0x2B,0x07,0xF8,0xDF,0xE6,0x16,0xC0,0x30,0x71,
	0x85,0xFD,0x72,0x95,0x29,0x79,0x0A,0x7B,0x46,0x11,0x7D,0x88,0x1D,0x2A,0x48,0x1F,
	0x45,0x89,0x47,0xEE,0xBB,0xBE,0x6E,0xC3,0x6C,0xCE,0x10,0x5A,0x2C,0xCA,0xFB,0xB2,
	0xCB,0x1C,0x9C,0xEC,0x2E,0x56,0x59,0x9B,0xA6,0x53,0xAE,0x17,0x25,0xC1,0x3F,0x6A,
	0x0F,0x09,0x01,0xA3,0xD6,0xA0,0xD8,0x08,0xE3,0x74,0x06,0x6D,0x19,0x98,0x1E,0x77,
	0x76,0xBC,0xEB,0x3C,0xB0,0xC4,0xC8,0x64,0x0E,0x86,0x63,0xD7,0xDB,0xBD,0xA7,0x82,
	0x39,0x4F,0x27,0xD2,0x5F,0x73,0xF4,0x75,0x6B,0xC2,0xD5,0x67,0x5D,0x80,0xAB,0x81,
	0xDE,0xF0,0xAD,0xAA,0xCD,0xB6,0xF6,0x7C,0xFC,0x33,0x05,0x14,0x96,0x15,0xC9,0x9E,
	0x35,0x5C,0x7E,0x44,0x54,0x58,0x3B,0x40,0x20,0xA8,0x8B,0x5E,0x4A,0x24,0x99,0x8E,
	0xF5,0xB5,0x62,0x00,0x37,0x5B,0x18,0x65,0x8D,0x32,0xE2,0xF9,0xDA,0x8A,0xD4,0xCC,
	0x26,0xF2,0xF1,0xE7,0x4B,0xC6,0xCF,0xFF,0x4C,0x84,0x61,0xFA,0xB8,0x0C,0xA9,0x50
  },
  inv[] = {
	0x74,0x85,0x96,0xA7,0xB8,0xC9,0xDA,0xEB,0xFC,0x0D,0x1E,0x2F,0x40,0x51,0x62,0x73,
	0x84,0x95,0xA6,0xB7,0xC8,0xD9,0xEA,0xFB,0x0C,0x1D,0x2E,0x3F,0x50,0x61,0x72,0x83,
	0x94,0xA5,0xB6,0xC7,0xD8,0xE9,0xFA,0x0B,0x1C,0x2D,0x3E,0x4F,0x60,0x71,0x82,0x93,
	0xA4,0xB5,0xC6,0xD7,0xE8,0xF9,0x0A,0x1B,0x2C,0x3D,0x4E,0x5F,0x70,0x81,0x92,0xA3,
	0xB4,0xC5,0xD6,0xE7,0xF8,0x09,0x1A,0x2B,0x3C,0x4D,0x5E,0x6F,0x80,0x91,0xA2,0xB3,
	0xC4,0xD5,0xE6,0xF7,0x08,0x19,0x2A,0x3B,0x4C,0x5D,0x6E,0x7F,0x90,0xA1,0xB2,0xC3,
	0xD4,0xE5,0xF6,0x07,0x18,0x29,0x3A,0x4B,0x5C,0x6D,0x7E,0x8F,0xA0,0xB1,0xC2,0xD3,
	0xE4,0xF5,0x06,0x17,0x28,0x39,0x4A,0x5B,0x6C,0x7D,0x8E,0x9F,0xB0,0xC1,0xD2,0xE3,
	0xF4,0x05,0x16,0x27,0x38,0x49,0x5A,0x6B,0x7C,0x8D,0x9E,0xAF,0xC0,0xD1,0xE2,0xF3,
	0x04,0x15,0x26,0x37,0x48,0x59,0x6A,0x7B,0x8C,0x9D,0xAE,0xBF,0xD0,0xE1,0xF2,0x03,
	0x14,0x25,0x36,0x47,0x58,0x69,0x7A,0x8B,0x9C,0xAD,0xBE,0xCF,0xE0,0xF1,0x02,0x13,
	0x24,0x35,0x46,0x57,0x68,0x79,0x8A,0x9B,0xAC,0xBD,0xCE,0xDF,0xF0,0x01,0x12,0x23,
	0x34,0x45,0x56,0x67,0x78,0x89,0x9A,0xAB,0xBC,0xCD,0xDE,0xEF,0x00,0x11,0x22,0x33,
	0x44,0x55,0x66,0x77,0x88,0x99,0xAA,0xBB,0xCC,0xDD,0xEE,0xFF,0x10,0x21,0x32,0x43,
	0x54,0x65,0x76,0x87,0x98,0xA9,0xBA,0xCB,0xDC,0xED,0xFE,0x0F,0x20,0x31,0x42,0x53,
	0x64,0x75,0x86,0x97,0xA8,0xB9,0xCA,0xDB,0xEC,0xFD,0x0E,0x1F,0x30,0x41,0x52,0x63  
};
void hash58(uint8_t buf[], int flen, uint64_t id) {
  int len = 18;
  uint8_t key[128] = {0x67,0x23,0xFE,0x30,0x45,0x33,0xF8,0x90,0x99,
		0x21,0x07,0xC1,0xD0,0x12,0xB2,0xA1,0x07,0x81};
  uint64_t a, b;
  for (;id > 0;id >>= 16) {
    a = id&0xFF;
    b = (id>>8)&0xFF;    
    a = a * b / gcd(a,b);
    if (a < 1) a = 1;
    b = a&0xFF;
    a >>= 8;
    key[len] = t0[a]*0xB5 - 0x03;
    key[len] = inv[key[len++]];
    key[len] = t1[a]*0xB7 + 0x49;
    key[len] = inv[key[len++]];
    key[len] = t0[b]*0xB5 - 0x03;
    key[len] = inv[key[len++]];
    key[len] = t1[b]*0xB7 + 0x49;
    key[len] = inv[key[len++]];
  }
  sha1(key, len);
  for (a = 0;a < 20;++a) key[a] ^= 0x36;
  for (;a < 64;++a) key[a] = 0x36;
  memcpy(buf, key, 64);
  sha1(buf, flen + 64);
  memcpy(buf + 64, buf, 20);
  for (a = 0;a < 64;++a) key[a] ^= 0x36^0x5c;
  memcpy(buf, key, 64);
  sha1(buf, 84);
}

void HashFile(FILE *fp, const char id_hex[]) {
  uint64_t id = 0, k;
  for(int i = 0;i < 8;++i) {
    sscanf(id_hex + i*2, "%02llX", &k);
    id |= k<<(i*8);
  }
  uint8_t nul[20] = {0};
  fseek(fp, 0x18, SEEK_SET);
  fwrite(nul, 1, 8, fp);
  fseek(fp, 0x32, SEEK_SET);
  fwrite(nul, 1, 20, fp);
  fseek(fp, 0x58, SEEK_SET);
  fwrite(nul, 1, 20, fp);
  nul[0] = 1;
  fseek(fp, 0x30, SEEK_SET);
  fwrite(nul, 1, 1, fp);  
  fseek(fp, 0, SEEK_END);
  int len = ftell(fp);
  uint8_t *buf = new uint8_t[len + 128];
  int tmp;
  tmp = fseek(fp, 0, SEEK_SET);
  tmp = fread(buf + 64, 1, len, fp);
  hash58(buf, len, id);
  tmp = fseek(fp, 0x58, SEEK_SET);
  puts("write hash");
  for (int a = 0;a < 20;++a)
    printf("%02x", buf[a]);
  puts("");  
  fwrite(buf, 1, 20, fp);
}

